/*
 * @lc app=leetcode.cn id=55 lang=golang
 *
 * [55] 跳跃游戏
 */

// 3. 从后往前贪心，最后看k是不是等于0
// @lc code=start
func canJump(nums []int) bool {
	k := len(nums) - 1
	for i := len(nums) - 1; i >= 0; i-- {
		if i+nums[i] >= k {
			k = i
		}
	}

	return k == 0
}

// @lc code=end

// 2. k是能跳到的最远距离，【i > k】代表永远走不到i,故false
// @lc code=start
func canJump(nums []int) bool {
	k := 0
	for i := 0; i < len(nums); i++ {
		if i > k {
			return false
		}
		k = max(k, i+nums[i])
	}

	return true
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

// 1. 深度优先 超时 71/172
// @lc code=start
func canJump(nums []int) (ans bool) {
	if len(nums) == 1 {
		return true
	}

	var dfs func(index int)
	dfs = func(index int) {
		for i := index - 1; i >= 0; i-- {
			if nums[i] >= index-i {
				if i == 0 {
					ans = true
					return
				}
				dfs(i)
			}
		}
	}
	dfs(len(nums) - 1)
	return ans
}

// @lc code=end

